Math of Freeciv/Battle outcome
This page describes in mathematical terms what will be the result of one unit attacking another. Probability of winning a fight The chances of winning a fight are sometimes counter-intuitive. E.g., what would you say are your chances of winning in the following situation (after taking into account the land advantages and other modifiers): you have an attack of 2 against a defense of 3, and the same number of hit points? Considering that the probability of winning each round is 2/5, you might think that this will give you with a reasonable chance of victory, something like 40%. Lost. You only have 19% chances of winning. The fact that the battle lasts several rounds tends to give a larger advantage to the biggest power than one could think beforehand. Supposing the reader is aware of the rules of the fight (for each round, take a random number, decide who wins that round, etc.), let's try to find a formula representing the chances of victory. Notations and basic computations Consider a unit having a strength (all modifications, field, city, unit experience of combat, etc. being applied) s and an enemy unit having a defense r . The number of hit points of the defending unit is written d_\text{hp} , the damages per victorious rounds from the attacking unit is a_\text{fp} . Let us note k the number of victorious rounds required to win the fight. And l is the number of rounds that, if lost, implies a defeat ( l is for "losing allowance"). When the attacking unit cause one damage per victorious rounds ( a_\text{fp}=1 ), k is the number of hit points of the defending unit ( d_\text{hp} ). More generally, : k = \lfloor\frac{d_\text{hp} + a_\text{fp} - 1}{a_\text{fp}}\rfloor . l may be computed similarily. The chance of winning each round, let us note it p , is : p = \frac{s}{s+r} . Thus the chance of losing a round is : q=1-p . Let us also denote m the maximal possible number of rounds fought. Usually, since each round results in some unit's loss of points and after a unit is defeated it can't strike any more and its enemy must keep at least one point, and the total number of possible losses is k+l , m is equal to : m_d= k+l-1 (variant of when it happens: attacker loses l-1 round and then wins until the victory). But since version 3.0 of Freeciv this number can be limited by ruleset; so, if m , there is some probability that both units survive the battle (limitation greater than or equal to m_d has no effect). Reasoning Now let us suppose that the fight takes n rounds to achieve, and let us compute the probability of victory. Note that we do not know n in advance but we suppose for now that it is given. For a given n , the probability of victory is the probability that k rounds have been won over these n tries and less than l rounds have been lost. If n < k + l , then the probability of victory is simply the probability that k rounds have been won over these n tries (as this implies that less than l rounds have been lost). In case of victory, the last round must be the final hit (otherwise the fight would have been stopped earlier). Apart from that, there must be k - 1 hits among the n - 1 other rounds. That probability is given by a binomial B(n-1,p) and is : {n-1 \choose k-1} p^{k-1} q^{n-k} . As the last round must be won, we multiply by p and get a probability of victory with n rounds of : P_{W n}={n-1 \choose k-1} p^k q^{n-k} . For the attacking unit to win the fight, we must have (assuming that m=m_d ) : k \leq n < k + l . Thus finally the probability of winning equals: : P_W=\sum_{n = k}^{k+l-1} {n-1 \choose k-1} p^k q^{n-k} .(1) Reasoning from the defeat count The freeciv source code uses a slightly different reasoning (look at ./common/combat.c:unit_win_chance() and ./common/combat.c:win_chance()). Let us note d the number of rounds lost, which must be smaller than l for a victorious attack. Then we have the following probability of victory: : P_W=\sum_{d = 0}^{l - 1} {k - 1 + d \choose d} p^{k-1} q^d p .(2) We get the formula (1) by using : n = k + d and : {n-1 \choose n-k} = {n-1 \choose k-1} . In the code, k is def_N_lose, l is att_N_lose, p is def_P_lose1, (1-p) is att_P_lose1, d is lr. Generalized reasoning Let's imagine that the fight always consists of m rounds, even if usually one of the parts in reality is killed before the number is reached; we now have a set of 2^m different imaginary battles. All the real fights have one or more items in this set for which actual rounds are matching real ones and the remaining ones are any possible sequence (for n -round battle, there are 2^{m-n} matching items). We can see that probability of the imaginary subset is equal to the probability of the real battle it matches (since first rounds are similar, following imaginary rounds are independent, and happening of any one of all possible combinations has the possibility of 1 ). Then, any sequence where k or more rounds are win matches to a won fight, and any one that has l or more rounds lost matches a lost fight (because m\le m_d , imaginary fight can't have l losses when in its real part there are k wins, etc.) Thus, we come again to the Bernoulli model: the probability of victory is equal to the probability of having k or more successes in B(m,p) series. This can be expressed using Bernoulli cumulative distribution function (possibility of getting k or less successes) : F_{B\:N,p}(k) = \sum_{i=0}^N {N \choose i}p^i (1-p)^{N-i} : the possibilities of winning, losing and "stalemate" are respectedly (if l\le m\ge k ) : P_W=1-F_{B\:m,p}(m-k-1) , : P_L=1-F_{B\:m,q}(m-l-1) , : P_S=1-P_W-P_L . The equivalence of (1), (2) and this form which, with m=m_d , expands as : P_W=1-\sum_{i=0}^{m-k}{m \choose i}p^i q^{m-i}= \sum_{i=k}^m {m \choose i}p^i q^{m-i} ,(3) can be clearly shown by algebraic transformations, just nobody have done it here yet. Approximate estimation of the winning chance Binomial distributions are mathematicians' lab mice and are well studied, thus, fast approximate ways to estimate such chances are known. Binomial random values are subject to the central limit theorem, and B(N,p) with sufficiently big N approaches normal distribution N(\mu=Np,\sigma=\sqrt{npq}) (first parameter is the mean and the second is the standard deviation of both distributions). The normal distribution is scalable from the standard one N(1,1) with cumulative function : \Phi(x)=\int_{-\infty}^x {e^{-{x^2\over 2}}\over \sqrt{2\pi}}dx , so that with the scaling function x(\alpha)=\frac{\alpha-\mu}{\sigma} : F_{B\:N,p}(k)\approx\Phi(x(k+0,5))-\Phi(x(-0,5)) , and thus : P_W\approx 1 - \Phi\left({m-k-mp+0,5\over \sqrt{mpq}}\right)+\Phi\left({-mp-0,5\over \sqrt{mpq}}\right) . Since \Phi(x<-3) <0,0015 and \Phi(x>3) > 0,9985 , we can be almost sure in the battle result if \left|mp-k\right|\over\sqrt{mpq} is outside of 3 interval without extra computations. In the interval, the function \Phi(x) is smooth and can be easily approximated by something fast. The trouble is that if p differs much from 0,5 , the N big enough for any credible value of this approximation goes very big. Top estimation of the error is : \Delta_{N max} = 0,7655\frac{p^2+q^2}{\sqrt{mpq}}\overset{p\ll0,5}\approx\frac{0,7655}{\sqrt{mp}} . Luckily, for small p 's works the Poisson distribution approximation P(\lambda=Np) , which parameter equals both mean and dispersion; for big possibilities, just switch p with q . The function is : F_{P\:\lambda}(k) = \sum_{i=0}^{k}\frac{\lambda^k e^{-\lambda}}{k!} , : P_W\overset{p\ll0,5}{\approx} 1-F_{P\:mp}(k) . The error is limited by \Delta_{P max}=\mathrm{min}(mp^2,p) . The Poisson distribution can't be scaled from a single curve, but the row itself is stabilizing fast enough. We can suggest which approximation is better by studying \Delta_{N max}/\Delta_{P max} . It's likely for m>1 that when it is over 2.3 normal one is better, and when under 1.125, the Poisson one, and in the uncertain gap taking the average of both gives good estimation (especially if the possibility is smaller than 50% since in this region these approximations tend to errate in opposite directions), but this idea requires better mathematical founding. The precision considering this all is about ±4% absolute, and might fit ±0.5% interval for m>10 . The remaining HP Well, maybe you will win. But won't your victory be Pyrrhic? Will your Mech._Inf. have enough HP retaining to defend the next turn from a warrior lurking nearby? Using aforementioned symbols, we can express winning attacker's health points remaining from initial a_\text{hp} after losing d rounds to a defender with firepower d_\text{fp} : a_\text{hp}' = a_\text{hp}-d\cdot d_\text{fp} , here d \in l-1 . Probability of having at least x, x\le a_\text{hp} hp remained in case of a victory we can express modifying the (2) equation : \mathrm P(a_\text{hp}'\ge x|\text{win}) = \mathrm P\left(d\le \left\lfloor \frac{a_\text{hp}-x}{d_\text{fp}}\right\rfloor=d_x\text{, suppose }d_x\le m|\text{win}\right)=\\ =\frac{1}{P_W}\sum_{d=0}^{d_x}{k - 1 + d \choose d} p^k q^d\text{.} If we express this using the imaginary battle concept, winning after losing d\le d_x rounds is equivalent to winning k or more rounds in a k+d_x -round battle, thus : \mathrm P(a_\text{hp}'\ge x|\text{win}) = \frac1{P_W}\sum_{i=k}^{k+d_x}{k+d_x\choose i}p^i q^{k+d_x-i}=\frac1{P_W}\left(1-F_{B\:k+d_x,p}(k-1)\right) . In battles which both units may survive, the probability of losing d_x or less rounds when this case happens (exactly m rounds are fought, m-k < d_x < l ) is : \mathrm P(a_\text{hp}'\ge x|\text{both survived})=\frac1{P_S}\left(\sum_{i=m-k+1}^{m-k+d_x}{m \choose i}p^i q^{m-i}\right)= : =\frac1{P_S}\left(F_{B\:m,p}(m-k+d_x)-F_{B\:m,p}(m-k)\right) . Thus, the overall chance of remaining alive and with a_\text{hp}'\ge x hitpoints after attacking your adversary is (when m-k < d_x=\left\lfloor \frac{a_\text{hp}-x}{d_\text{fp}}\right\rfloor < l ) : \mathrm P(a_\text{hp}'\ge x)=P_W \mathrm P(...|\text{win})+P_S \mathrm P(...|\text{both survived})= : =1-F_{B\:k+d_x,p}(k-1)+F_{B\:m,p}(m-k+d_x)-F_{B\:m,p}(m-k) . The binomial functions here may be approximated for each point in a way similar to aforementioned, just the characteristics (mean, dispersion...) of the distribution of d are not so obvious. Results of a battle of several units Let's consider a simplest case of an action where several units participate: n units in one turn attack one defender. The optimal order of attacking a target is a question out of the scope of this article, presume that the order of the attackers is predefined. Let each of them has losing limit to defender's defence l_i and attack strength s_i , i=1, ..., n by the order of attack. What is the chance of the defender to survive the attacks and have hitpoints d_{\text{hp}n} afterwards? To answer this question precisely, we must also take into account the probability p_\text{vet}(v_{i-1}) for the defender who survived an i -th match to get a veteran rank v_i and thus a strength bonus b(v_i) : the defender strength against each one is r_i=r_0 b(v_{i-1}) . This number is in general not independent from d_{\text{hp}n} since units that have got the status earlier tend to preserve more hp. The formulation for the possibility of given defender state will be recurrent, based on calculation for cases if the defender has got the latest status in the latest match or earlier: : \mathrm P(d_{\text{hp}n}=h_n, d_{\text{v}n}=v_n) = \sum_{h_{n-1}=h_n}^{d_{\text{hp}0}}\Big(\\ \mathrm P(d_{\text{hp}n-1}=h_{n-1}, d_{\text{v}n}=v_n-1)p_\text{vet}(v_n-1)\mathrm P(w=\frac{h_{n-1}-h_n}{a_{\text{fp}i}}|h_{n-1},s_i, r_0b(v_n-1),l_i)+ : +\mathrm P(d_{\text{hp}n-1}=h_{n-1}, d_{\text{v}n}=v_n)(1-p_\text{vet}(v_n))\mathrm P(w=\frac{h_{n-1}-h_n}{a_{\text{fp}i}}|h_{n-1},s_i, r_0b(v_n),l_i)\Big) , where probabilities of winning w rounds for attacker (before not winning the match) is calculated by swapping roles in formulae for d above, with zeroes for non-integer values. While this formula is not an easy thing to compute, the case when firepowers and strengthes of the attackers are the same and the probability of getting veteran status is zero or neglectable (even if it is nonzero, the veteran status is not obtained with probability (1-p_\text{vet})^n ) is more like a single match. We can think that we have a single attacker with the same strength and firepower as a single unit and losing capacity L=\sum_{i=1}^n l_i , and then just apply aforementioned formulae. Category:Technical docs